An Algorithmic Framework for Strategic Fair Division

摘要

We study the paradigmatic fair division problem of allocating a divisiblegood among agents with heterogeneous preferences, commonly known as cakecutting. Classical cake cutting protocols are susceptible to manipulation. Dotheir strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, by designinga concrete computational framework for fair division---the class of GeneralizedCut and Choose (GCC) protocols}---and reasoning about the game-theoreticproperties of algorithms that operate in this model. The class of GCC protocolsincludes the most important discrete cake cutting protocols, and turns out tobe compatible with the study of fair division among strategic agents. Inparticular, GCC protocols are guaranteed to have approximate subgame perfectNash equilibria, or even exact equilibria if the protocol's tie-breaking ruleis flexible. We further observe that the (approximate) equilibria ofproportional GCC protocols---which guarantee each of the $n$ agents a$1/n$-fraction of the cake---must be (approximately) proportional. Finally, wedesign a protocol in this framework with the property that its Nash equilibriumallocations coincide with the set of (contiguous) envy-free allocations.